// 1. 对给定的图，建立图的邻接矩阵；并实现该图的深度优先搜索遍历和广度优先搜索遍历。
// 2.对给定的图，建立图的邻接表；并实现该图的深度优先搜索遍历和广度优先搜索遍历。

// 这里是使用邻接矩阵

#include "stdio.h"
#include "stdlib.h"

#define MaxVertexNum 20                            //定义图的最大顶点数
#define MaxEdgeNum 50                              //定义图的最大边数
#define MaxValue 1000                              //定义MaxValue为全局整型常量，作为无穷大
typedef int VertexType;                            //定义图中顶点数据的类型VertexType为整型
typedef VertexType vexlist[MaxVertexNum];          //为存储顶点信息的数组类型
typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; //为存储邻接矩阵的数组类型
int n;                                             //实际的顶点个数
int e;                                             //实际的边个数
int visited[MaxVertexNum];                         //全局数组标记置1表示已经访问，0为未访问

/*
查找顶点在顶点数组中的下标
params GV 顶点数组
params vertex 要查找的顶点
params vertexNumer 顶点数组的长度
return 顶点在顶点数组中的下标
*/
int getVextexIndex(vexlist GV, int vertex, int vertexNumer)
{
    int vertexIndex = 0;
    for (int i = 0; i < vertexNumer; i++)
    {
        if (GV[i] == vertex)
        {
            vertexIndex = i;
        }
    }
    return vertexIndex;
}

/*
查看一个顶点是否已经被访问
* params vertex 顶点
* return 1:已经访问 0:没有被访问 
*/
int getVertexStatus(int vertex)
{
    int res = 0;
    for (int i = 0; i < MaxVertexNum; i++)
    {
        if (vertex == visited[i])
        {
            res = 1;
            break;
        }
    }
    return res;
}

/* 建立图的邻接矩阵
通过从键盘上输入n个顶点信息和e条无向带权边的信息，建立邻接矩阵GA*/
void Create(vexlist GV, adjmatrix GA, int vertexNumer, int sideNumber)
{
    // 输入的顶点数据
    int vertexInputValue;

    // 边的两个顶点
    int vertex1;

    int verter_next;

    // 边的两个顶点在顶点数组中的下标
    int vertex1Index;
    int vertex2Index;

    // 边的权值
    int sideWeight;

    printf("\n请输入 %d 个顶点数据\n", vertexNumer); //建立顶点数组
    for (int i = 1; i <= vertexNumer; i++)
    {
        printf("请输入第%d个顶点数据\n", i);
        scanf("%d", &vertexInputValue);
        GV[i - 1] = vertexInputValue;
    }

    //初始化默认权为无穷的邻接矩阵数组
    for (int i = 0; i < vertexNumer; i++)
    {
        for (int j = 0; j < vertexNumer; j++)
        {
            GA[i][j] = MaxValue;
        }
    }
    // 根据边更新邻接矩阵的权值
    printf("输入 %d 条无向带权边\n", sideNumber); /*建立邻接矩阵数组*/
    for (int k = 1; k <= sideNumber; k++)
    {
        printf("输入第 %d 条边的两端序号及权值(i j W): \n", k);
        scanf("%d%d%d", &vertex1, &verter_next, &sideWeight);
        // 查找对应下标去更新权值
        vertex1Index = getVextexIndex(GV, vertex1, vertexNumer);
        vertex2Index = getVextexIndex(GV, verter_next, vertexNumer);
        GA[vertex1Index][vertex2Index] = sideWeight;
    }
}

/*
图GA的深度优先遍历 - 递归实现
*/
void dfs(vexlist GV, adjmatrix GA, int vertex, int vertexNumer) // 从顶点i出发的深度遍历
{

    // 已经访问过
    int index = getVextexIndex(GV, vertex, vertexNumer);
    visited[index] = 1;
    // printf("%d结点已经被访问,下标为%d已经置1\n", vertex, index);
    printf("%d \t", vertex);
    for (int i = 0; i < vertexNumer; i++)
    {
        // printf("%d\t", GA[index][i]);
        if (GA[index][i] != MaxValue && visited[i] == 0)
        {
            // printf("\n找到了%d结点下一个要去的结点%d\n", vertex, GV[i]);
            dfs(GV, GA, GV[i], vertexNumer);
        }
    }
}

/**
 * 图GA的深度优先遍历 - 非递归实现
 * TODO: 使用一个简易数组模拟栈实现非递归的深度优先遍历
 * 递归实际上也只是一个看不见的栈
 */
void dfsBystack(vexlist GV, adjmatrix GA, int vertex, int vertexNumer)
{
}

//邻接矩阵的广度遍历
void bfs(vexlist GV, adjmatrix GA, int vertex, int vertexNumer) //从顶点i出发广度遍历
{
    //非递归,使用数组模拟队列 有点像二叉树的层级遍历 尽可能的往下走去访问
    int front;
    int rear;
    int queue[MaxVertexNum];
    front = rear = -1;
    //  输出当前结点
    printf("%d\t", vertex);
    // 将该结点标记为已经访问过了
    int index = getVextexIndex(GV, vertex, vertexNumer);
    // printf("\n%d结点已经被访问,下标为%d已经置1\n", vertex, index);
    visited[index] = 1;
    // 将结点入队
    queue[++rear] = vertex;
    while (front != rear)
    {
        // 出队
        vertex = queue[++front];
        for (int i = 0; i < vertexNumer; i++)
        {
            // printf("%d\t", GA[index][i]);
            // 找到链接的结点且是没有访问过的结点
            if (GA[getVextexIndex(GV, vertex, vertexNumer)][i] != MaxValue && visited[i] == 0)
            {
                // 访问该结点
                printf("%d\t",GV[i]);
                // 同时将该结点进行已访问标记
                visited[getVextexIndex(GV, GV[i], vertexNumer)] = 1;
                // 将这个访问的元素入队
                queue[++rear] = GV[i];
            }
        }
    }
}

/**
 * 打印图GA的邻接矩阵
 * params GA 图
 * params vertexNumer 图的顶点个数
 */
void print(adjmatrix GA, int vertexNumer)
{
    for (int i = 0; i < vertexNumer; i++)
    {
        for (int j = 0; j < vertexNumer; j++)
        {
            printf("%d\t", GA[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    // 顶点一维数组
    vexlist GV;
    // 二维数组
    adjmatrix GA;
    int i, k;
    // 顶点数
    int vertexNumer;
    // 边的数量
    int sideNumber;
    do
    {
        printf("\n\n\n\n");
        printf("\t\t      图的邻接矩阵子系统\n");
        printf("\t\t*****************************\n");
        printf("\t\t*       1----更 新 图　 　  *\n");
        printf("\t\t*       2----深度遍历　　　 *\n");
        printf("\t\t*       3----广度遍历　　　 *\n");
        printf("\t\t*       0----返　　回　　 　*\n");
        printf("\t\t*****************************\n");
        printf("\t\t   请选择菜单项(0－3)：");
        scanf("%d", &k);
        switch (k)
        {
        case 1:
            printf("\n请输入图的顶点的个数vertexNumer=");
            scanf("%d", &vertexNumer);
            printf("请输入图的边的的个数sideNumber=");
            scanf("%d", &sideNumber);
            Create(GV, GA, vertexNumer, sideNumber);
            printf("\n图的邻接矩阵如下\n");
            print(GA, vertexNumer);
            break;
        case 2:
            // 深度优先遍历
            // 已经访问过的结点的初始化
            // 已经访问过的初始化0
            for (int i = 0; i < vertexNumer; i++)
            {
                visited[i] = 0;
            }
            int vertexValue;
            printf("\n请输入从图的哪个顶点开始深度遍历:\n");
            scanf("%d", &vertexValue);
            printf("深度遍历序列是:\n");
            dfs(GV, GA, vertexValue, vertexNumer);
            break;
        case 3:
            // 广度优先遍历
            for (int i = 0; i < vertexNumer; i++)
            {
                visited[i] = 0;
            }
            int vertexValue2;
            printf("\n请输入从图的哪个顶点开始广度遍历:\n");
            scanf("%d", &vertexValue2);
            printf("广度遍历序列是:\n");
            bfs(GV, GA, vertexValue2, vertexNumer);
            break;

        case 0:
            // 结束控制台循环
            break;
        }
    } while (k != 0);
    return 0;
}